|
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges. The McGee graph is the unique (3,7)-cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage that is not a Moore graph. First discovered by Sachs but unpublished,〔Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960〕 the graph is named after McGee who published the result in 1960.〔McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960〕 Then, the McGee graph was the proven the unique (3,7)-cage by Tutte in 1966.〔Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966〕〔Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982〕〔Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989〕 The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of five non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these five graphs is the generalized Petersen graph , also known as the Nauru graph.〔 .〕〔.〕 The McGee graph has radius 4, diameter 4, chromatic number 3 and chromatic index 3. It is also a 3-vertex-connected and a 3-edge-connected graph. ==Algebraic properties== The characteristic polynomial of the McGee graph is : . The automorphism group of the McGee graph is of order 32 and doesn't acts transitively upon its vertices: there are two vertex orbits, of lengths 8 and 16. The McGee graph is the smallest cubic cage that is not a vertex-transitive graph.〔Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「McGee graph」の詳細全文を読む スポンサード リンク
|